<!DOCTYPE html>
<html  lang="en">
<head>
    <meta charset="utf-8" />

<meta name="generator" content="Hexo 4.2.0" />

<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />

<title>N皇后（N-Queens） - KZ.LOKKA</title>


    <meta name="description" content="LeetCode 51 N-Queens LeetCode 52 N-Queens II Lanqiao BASIC-27 2N-Queens Lanqiao ADV-203 8-Queens">
<meta property="og:type" content="article">
<meta property="og:title" content="N皇后（N-Queens）">
<meta property="og:url" content="http://lokka.me/blog/problem/200408-n-queens/index.html">
<meta property="og:site_name" content="KZ.LOKKA">
<meta property="og:description" content="LeetCode 51 N-Queens LeetCode 52 N-Queens II Lanqiao BASIC-27 2N-Queens Lanqiao ADV-203 8-Queens">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="http://lokka.me/blog/problem/200408-n-queens/chess-pieces-child.jpg">
<meta property="article:published_time" content="2020-04-07T16:17:25.000Z">
<meta property="article:modified_time" content="2020-04-25T11:31:27.057Z">
<meta property="article:author" content="Kain Zhang">
<meta property="article:tag" content="LeetCode">
<meta property="article:tag" content="Lanqiao">
<meta property="article:tag" content="BackTracking">
<meta property="article:tag" content="DFS">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://lokka.me/blog/problem/200408-n-queens/chess-pieces-child.jpg">







<link rel="icon" href="/images/favicon.svg">


<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bulma@0.7.2/css/bulma.css">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.4.1/css/all.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Ubuntu:400,600|Source+Code+Pro">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@9.12.0/styles/atom-one-light.css">


    
    
<style>body>.footer,body>.navbar,body>.section{opacity:0}</style>

    
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/css/lightgallery.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/css/justifiedGallery.min.css">

    
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.css">

    
    
    
    
<link rel="stylesheet" href="/css/back-to-top.css">

    
    
    
    
    
    
    
    <link rel="stylesheet" href="/css/progressbar.css">
<script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>
    
    
    


<link rel="stylesheet" href="/css/style.css">
</head>
<!-- <body class="is-2-column"> -->
<body class="is-3-column">
    <nav class="navbar navbar-main">
    <div class="container">
        <div class="navbar-brand is-flex-center">
            <a class="navbar-item navbar-logo" href="/">
            
                <img src="/images/logo.svg" alt="N皇后（N-Queens）" height="28">
            
            </a>
        </div>
        <div class="navbar-menu">
            
            <div class="navbar-start">
                
                <a class="navbar-item"
                href="/">Home</a>
                
                <a class="navbar-item"
                href="/archives">Archives</a>
                
                <a class="navbar-item"
                href="/categories">Categories</a>
                
                <a class="navbar-item"
                href="/tags">Tags</a>
                
            </div>
            
            <div class="navbar-end">
                
                
                <a class="navbar-item is-hidden-tablet catalogue" title="Catalogue" href="javascript:;">
                    <i class="fas fa-list-ul"></i>
                </a>
                
                
                <a class="navbar-item search" title="Search" href="javascript:;">
                    <i class="fas fa-search"></i>
                </a>
                
            </div>
        </div>
    </div>
</nav>
    
    <section class="section">
        <div class="container">
            <div class="columns">
                <div class="column is-8-tablet is-8-desktop is-8-widescreen has-order-2 column-main">
<div class="card">
    
    <div class="card-image">
        <span  class="image is-7by1">
            <img class="thumbnail" src="/blog/problem/200408-n-queens/chess-pieces-child.jpg" alt="N皇后（N-Queens）">
        </span>
    </div>
    
    <div class="card-content article ">
        
        <div class="level article-meta is-size-7 is-uppercase is-mobile is-overflow-x-auto">
            <div class="level-left">
                <!-- <time class="level-item has-text-grey" datetime="2020-04-07T16:17:25.000Z">2020-04-08</time> -->
                <time class="level-item has-text-grey" datetime="2020-04-07T16:17:25.000Z">
                    <i class="far fa-calendar-alt">&nbsp;</i>2020-04-08
                </time>
                
                <time class="level-item has-text-grey is-hidden-mobile" datetime="2020-04-25T11:31:27.057Z">
                    <i class="far fa-calendar-check">&nbsp;</i>2020-04-25
                </time>
                
                
                <div class="level-item">
                <i class="far fa-folder has-text-grey">&nbsp;</i>
                <a class="has-link-grey -link" href="/categories/Note/">Note</a>&nbsp;/&nbsp;<a class="has-link-grey -link" href="/categories/Note/Problem/">Problem</a>
                </div>
                
                
                <i class="far fa-clock has-text-grey is-hidden-mobile">&nbsp;</i>
                <span class="level-item has-text-grey is-hidden-mobile">
                    
                    
                    15 minutes read (About 2322 words)
                </span>
                
                
            </div>
        </div>
        
        <h1 class="title is-size-3 is-size-4-mobile has-text-weight-normal">
            
                N皇后（N-Queens）
            
        </h1>
        <div class="content">
            <ul>
<li>LeetCode 51 N-Queens</li>
<li>LeetCode 52 N-Queens II</li>
<li>Lanqiao BASIC-27 2N-Queens</li>
<li>Lanqiao ADV-203 8-Queens</li>
</ul>
<a id="more"></a>

<hr>
<h2 id="N-Queens"><a href="#N-Queens" class="headerlink" title="N-Queens"></a>N-Queens</h2><h3 id="Description"><a href="#Description" class="headerlink" title="Description"></a>Description</h3><p>&emsp;&emsp;n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。</p>
<p>&emsp;&emsp;<img src="/blog/problem/200408-n-queens/8-queens.png" class title="8-queens"></p>
<p>&emsp;&emsp;上图为 8 皇后问题的一种解法。</p>
<p>&emsp;&emsp;给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。</p>
<p>&emsp;&emsp;每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。</p>
<p>&emsp;&emsp;<strong>原题：</strong><a href="https://leetcode-cn.com/problems/n-queens" title="N-Queens">LeetCode 51 N-Queens</a></p>
<h3 id="Sample"><a href="#Sample" class="headerlink" title="Sample"></a>Sample</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">输入: 4</span><br><span class="line"></span><br><span class="line">输出: [</span><br><span class="line"> [&quot;.Q..&quot;,  &#x2F;&#x2F; 解法 1</span><br><span class="line">  &quot;...Q&quot;,</span><br><span class="line">  &quot;Q...&quot;,</span><br><span class="line">  &quot;..Q.&quot;],</span><br><span class="line"></span><br><span class="line"> [&quot;..Q.&quot;,  &#x2F;&#x2F; 解法 2</span><br><span class="line">  &quot;Q...&quot;,</span><br><span class="line">  &quot;...Q&quot;,</span><br><span class="line">  &quot;.Q..&quot;]</span><br><span class="line">]</span><br><span class="line"></span><br><span class="line">解释: 4 皇后问题存在两个不同的解法。</span><br></pre></td></tr></table></figure>

<h3 id="Thought"><a href="#Thought" class="headerlink" title="Thought"></a>Thought</h3><p>&emsp;&emsp;题目要求将n个皇后放置在n * n大小的棋盘上，皇后之间不能打架，也就是每行、每列、每条对角线上不能同时有两位皇后。</p>
<p>&emsp;&emsp;思路就是深搜回溯，从第1行开始每次逐列放置皇后，每次放置时对已经放置完成的行进行判断，能放则放，不能放则弃。也就是检查当前位置皇后的上、左上、右上方是否存在皇后。完成n个皇后放置任务后将当前棋盘添加至结果集。</p>
<h3 id="Code"><a href="#Code" class="headerlink" title="Code"></a>Code</h3><p>&emsp;&emsp;觉得这题难度其实不大，就是个人在效率上有点难受（再见残酷的世界！），第1版写完交上去虽然一次AC了，但时间和空间居然都被95%的人碾压？？？（拐回来看代码发现参数全是形参，改了引用参数后时间击败60%空间击败100%）然后参考老哥们的题解改了改，还凑合吧，粘两个版本留念。</p>
<h4 id="Version-1"><a href="#Version-1" class="headerlink" title="Version 1"></a>Version 1</h4><p>&emsp;&emsp;直接把整个棋盘开出来了，然后逐行放置皇后。检查已放置的行就开了3个for循环，分别对正上、左上、右上的格子进行遍历判断。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">isValid</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt;&amp; bd, <span class="keyword">int</span> row, <span class="keyword">int</span> col)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//正上</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; row; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(bd[i][col] == <span class="string">'Q'</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//左上</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = row - <span class="number">1</span>, j = col - <span class="number">1</span>; i &gt;= <span class="number">0</span> &amp;&amp; j &gt;= <span class="number">0</span>; i--, j--) &#123;</span><br><span class="line">            <span class="keyword">if</span>(bd[i][j] == <span class="string">'Q'</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//右上</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = row - <span class="number">1</span>, j = col + <span class="number">1</span>; i &gt;= <span class="number">0</span> &amp;&amp; j &lt; bd.size(); i--, j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(bd[i][j] == <span class="string">'Q'</span>) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt;&amp; bd, <span class="keyword">int</span> row, <span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(row == n) &#123;</span><br><span class="line">            res.push_back(bd);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(isValid(bd, row, i)) &#123;</span><br><span class="line">                bd[row][i] = <span class="string">'Q'</span>;</span><br><span class="line">                dfs(bd, row + <span class="number">1</span>, n);</span><br><span class="line">                bd[row][i] = <span class="string">'.'</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt;&gt; <span class="title">solveNQueens</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">        <span class="function"><span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt; <span class="title">bd</span><span class="params">(n, <span class="built_in">string</span>(n, <span class="string">'.'</span>))</span></span>;</span><br><span class="line">        dfs(bd, <span class="number">0</span>, n);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt;&gt; res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<h4 id="Version-2"><a href="#Version-2" class="headerlink" title="Version 2"></a>Version 2</h4><p>&emsp;&emsp;棋盘是按行开辟的，凑够一整盘后带走放入结果集（空间上没有影响，就是单纯尝试下。。。）</p>
<p>&emsp;&emsp;这个判断比较有意思，是在题解区学的。先开个数组用来存放棋盘每一行放置皇后的列值，在判断时，如果当前列与数组中的列重复，即正上方有皇后。对角线点坐标的x, y与当前点相减的绝对值是相同的，由此判断对角线上是否存在皇后。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">isValid</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &amp;pos)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; row; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (col == pos[i] || <span class="built_in">abs</span>(row - i) == <span class="built_in">abs</span>(pos[i] - col))</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> n, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &amp;pos, <span class="built_in">string</span> &amp;line)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (row == n) &#123;</span><br><span class="line">            res.push_back(tmp);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (isValid(row, i, pos)) &#123;</span><br><span class="line">                line[i] = <span class="string">'Q'</span>;</span><br><span class="line">                tmp.push_back(line);</span><br><span class="line">                line[i] = <span class="string">'.'</span>;</span><br><span class="line">                pos[row] = i;</span><br><span class="line">                dfs(row + <span class="number">1</span>, n, pos, line);</span><br><span class="line">                pos[row] = <span class="number">-1</span>;</span><br><span class="line">                tmp.pop_back();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt;&gt; <span class="title">solveNQueens</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">        <span class="function"><span class="built_in">string</span> <span class="title">line</span><span class="params">(n, <span class="string">'.'</span>)</span></span>;</span><br><span class="line">        <span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">pos</span><span class="params">(n, <span class="number">-1</span>)</span></span>;</span><br><span class="line">        dfs(<span class="number">0</span>, n, pos, line);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt;&gt; res;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="built_in">string</span>&gt; tmp;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<p>&emsp;</p>
<hr>
<h2 id="N-Queen-II"><a href="#N-Queen-II" class="headerlink" title="N-Queen II"></a>N-Queen II</h2><h3 id="Description-1"><a href="#Description-1" class="headerlink" title="Description"></a>Description</h3><p>&emsp;&emsp;n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。</p>
<p>&emsp;&emsp;<img src="/blog/problem/200408-n-queens/8-queens.png" class title="8-queens"></p>
<p>&emsp;&emsp;上图为 8 皇后问题的一种解法。</p>
<p>&emsp;&emsp;给定一个整数 n，返回 n 皇后不同的解决方案的数量。</p>
<p>&emsp;&emsp;<strong>原题：</strong><a href="https://leetcode-cn.com/problems/n-queens-ii" title="N-Queens">LeetCode 52 N-Queens II</a></p>
<h3 id="Sample-1"><a href="#Sample-1" class="headerlink" title="Sample"></a>Sample</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">输入: 4</span><br><span class="line"></span><br><span class="line">输出: 2</span><br><span class="line"></span><br><span class="line">解释: 4 皇后问题存在如下两个不同的解法。</span><br><span class="line">[</span><br><span class="line"> [&quot;.Q..&quot;,  &#x2F;&#x2F; 解法 1</span><br><span class="line">  &quot;...Q&quot;,</span><br><span class="line">  &quot;Q...&quot;,</span><br><span class="line">  &quot;..Q.&quot;],</span><br><span class="line"></span><br><span class="line"> [&quot;..Q.&quot;,  &#x2F;&#x2F; 解法 2</span><br><span class="line">  &quot;Q...&quot;,</span><br><span class="line">  &quot;...Q&quot;,</span><br><span class="line">  &quot;.Q..&quot;]</span><br><span class="line">]</span><br></pre></td></tr></table></figure>

<h3 id="Thought-1"><a href="#Thought-1" class="headerlink" title="Thought"></a>Thought</h3><p>&emsp;&emsp;怎么说呢，我严重怀疑LeetCode的临时工把题号标错了，这个虽然是II，但明显是原版的简化。看见题就没多想，直接复制粘贴上一题代码，删掉所有棋盘数据，只保留存放每行皇后位置的数组，跑都没跑就提交了（也就这时候敢浪）。在题解区看到用位运算好像效率蛮高的，改（有）天（缘）再看吧。</p>
<h3 id="Code-1"><a href="#Code-1" class="headerlink" title="Code"></a>Code</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> &#123;</span></span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">isValid</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &amp;pos)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; row; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (col == pos[i] || <span class="built_in">abs</span>(row - i) == <span class="built_in">abs</span>(pos[i] - col))</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> n, <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; &amp;pos, <span class="keyword">int</span> &amp;res)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (row == n) &#123;</span><br><span class="line">            res++;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (isValid(row, i, pos)) &#123;</span><br><span class="line">                pos[row] = i;</span><br><span class="line">                dfs(row + <span class="number">1</span>, n, pos, res);</span><br><span class="line">                pos[row] = <span class="number">-1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">totalNQueens</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</span><br><span class="line">        <span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">pos</span><span class="params">(n, <span class="number">-1</span>)</span></span>;</span><br><span class="line">        <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line">        dfs(<span class="number">0</span>, n, pos, res);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<p>&emsp;</p>
<hr>
<h2 id="2N-Queens"><a href="#2N-Queens" class="headerlink" title="2N-Queens"></a>2N-Queens</h2><h3 id="Description-2"><a href="#Description-2" class="headerlink" title="Description"></a>Description</h3><p>&emsp;&emsp;给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。</p>
<ul>
<li>Input:</li>
</ul>
<p>&emsp;&emsp;输入的第一行为一个整数n，表示棋盘的大小。</p>
<p>&emsp;&emsp;接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。</p>
<ul>
<li>Output:</li>
</ul>
<p>&emsp;&emsp;输出一个整数，表示总共有多少种放法。</p>
<h3 id="Sample-2"><a href="#Sample-2" class="headerlink" title="Sample"></a>Sample</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">输入:   &#x2F;&#x2F; Sample 1</span><br><span class="line">4</span><br><span class="line">1 1 1 1</span><br><span class="line">1 1 1 1</span><br><span class="line">1 1 1 1</span><br><span class="line">1 1 1 1</span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line">2</span><br><span class="line"></span><br><span class="line">输入:   &#x2F;&#x2F; Sample 2</span><br><span class="line">4</span><br><span class="line">1 0 1 1</span><br><span class="line">1 1 1 1</span><br><span class="line">1 1 1 1</span><br><span class="line">1 1 1 1</span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line">0</span><br></pre></td></tr></table></figure>

<h3 id="Thought-2"><a href="#Thought-2" class="headerlink" title="Thought"></a>Thought</h3><p>&emsp;&emsp;和N皇后的思路一样，区别是放置两种颜色的皇后，也就是黑白皇后各来一次深搜。根据题意，棋盘上1代表可以放置，0代表不可放置。用2表示白皇后，用3表示黑皇后。放置白皇后时遇到0跳过，放置黑皇后时遇到0和2跳过，两种颜色全部放完时（q == 4)结束并计数。</p>
<h3 id="Code-2"><a href="#Code-2" class="headerlink" title="Code"></a>Code</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> n, bd[<span class="number">10</span>][<span class="number">10</span>], res = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isValid</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col, <span class="keyword">int</span> q)</span> </span>&#123;  <span class="comment">// q 为皇后类型</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> r = row - <span class="number">1</span>, t = <span class="number">1</span>; r &gt;= <span class="number">0</span>; r--, t++ ) &#123;</span><br><span class="line">        <span class="keyword">if</span> (bd[r][col] == q</span><br><span class="line">            || (col - t &gt;= <span class="number">0</span> &amp;&amp; bd[r][col - t] == q)</span><br><span class="line">            || (col + t &lt; n &amp;&amp; bd[r][col + t] == q)) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> q)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (q == <span class="number">4</span>) &#123;       <span class="comment">// 黑白皇后均已放完</span></span><br><span class="line">        res++;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (row == n) &#123;</span><br><span class="line">        dfs(<span class="number">0</span>, q + <span class="number">1</span>);  <span class="comment">// 放置另一种颜色的皇后</span></span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> col = <span class="number">0</span>; col &lt; n; col++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (bd[row][col] == <span class="number">0</span> || bd[row][col] == <span class="number">2</span>)</span><br><span class="line">            <span class="keyword">continue</span>;</span><br><span class="line">        <span class="keyword">if</span> (isValid(row, col, q)) &#123;</span><br><span class="line">            bd[row][col] = q;</span><br><span class="line">            dfs(row + <span class="number">1</span>, q);</span><br><span class="line">            bd[row][col] = <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++)</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;bd[i][j]);</span><br><span class="line">    dfs(<span class="number">0</span>, <span class="number">2</span>);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; res &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>&emsp;</p>
<hr>
<h2 id="8-Queens"><a href="#8-Queens" class="headerlink" title="8-Queens"></a>8-Queens</h2><h3 id="Description-3"><a href="#Description-3" class="headerlink" title="Description"></a>Description</h3><p>&emsp;&emsp;规则同8皇后问题，但是棋盘上每格都有一个数字，要求八皇后所在格子数字之和最大。</p>
<ul>
<li>Input:</li>
</ul>
<p>&emsp;&emsp;一个8*8的棋盘。</p>
<ul>
<li>Ouput:</li>
</ul>
<p>&emsp;&emsp;所能得到的最大数字和</p>
<h3 id="Sample-3"><a href="#Sample-3" class="headerlink" title="Sample"></a>Sample</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">输入:</span><br><span class="line">1 2 3 4 5 6 7 8</span><br><span class="line">9 10 11 12 13 14 15 16</span><br><span class="line">17 18 19 20 21 22 23 24</span><br><span class="line">25 26 27 28 29 30 31 32</span><br><span class="line">33 34 35 36 37 38 39 40</span><br><span class="line">41 42 43 44 45 46 47 48</span><br><span class="line">48 50 51 52 53 54 55 56</span><br><span class="line">57 58 59 60 61 62 63 64</span><br><span class="line"></span><br><span class="line">输出:</span><br><span class="line">260</span><br><span class="line"></span><br><span class="line">数据规模和约定: 棋盘上的数字范围 0~99</span><br></pre></td></tr></table></figure>

<h3 id="Thought-3"><a href="#Thought-3" class="headerlink" title="Thought"></a>Thought</h3><p>&emsp;&emsp;依然是深搜回溯，各个位置的数字已经给了，并且题目说明了数字范围为0~99，所以我们将访问的数字累加，并将值改为-1表示已经访问过，确保不被重复访问。每次满足终止条件时，比较当前放置方法的数字之和，取最大值即可。</p>
<h3 id="Code-3"><a href="#Code-3" class="headerlink" title="Code"></a>Code</h3><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> n = <span class="number">8</span>, bd[<span class="number">10</span>][<span class="number">10</span>], res = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">isValid</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> r = row - <span class="number">1</span>, t = <span class="number">1</span>; r &gt;= <span class="number">0</span>; r--, t++ ) &#123;</span><br><span class="line">        <span class="keyword">if</span> (bd[r][col] == <span class="number">-1</span></span><br><span class="line">            || (col - t &gt;= <span class="number">0</span> &amp;&amp; bd[r][col - t] == <span class="number">-1</span>)</span><br><span class="line">            || (col + t &lt; n &amp;&amp; bd[r][col + t] == <span class="number">-1</span>)) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> sum)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (row == n) &#123;</span><br><span class="line">        res = max(res, sum);</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> col = <span class="number">0</span>; col &lt; n; col++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (isValid(row, col)) &#123;</span><br><span class="line">            <span class="keyword">int</span> tmp = bd[row][col];</span><br><span class="line">            bd[row][col] = <span class="number">-1</span>;</span><br><span class="line">            dfs(row + <span class="number">1</span>, sum + tmp);</span><br><span class="line">            bd[row][col] = tmp;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n; j++)</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;bd[i][j]);</span><br><span class="line"></span><br><span class="line">    dfs(<span class="number">0</span>, <span class="number">0</span>);</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; res &lt;&lt; <span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>&emsp;</p>
<hr>
<h2 id="Summary"><a href="#Summary" class="headerlink" title="Summary"></a>Summary</h2><p>&emsp;&emsp;总得来说就是简单的暴力深搜回溯，逻辑上没什么细节好抠的。虽然LeetCode标记的难度是Hard，但实际其实还好？不过第一次信心满满地交上去，结果时间和空间都只击败5%真的难受（弱鸡枯了），确实自己经常粗心忘打取地址符，导致内存使用翻倍，尤其是变量名很长的时候都是习惯性复制粘贴，就忘了。</p>
<p>&emsp;&emsp;蓝桥的比LeetCode难度稍大，比较有意思的是蓝桥的2N皇后被放在“基础练习”的试题集，而相较而言更简单的8皇后被放在“算法提高”？？？可能跟LeetCode是同一个临时工吧哈哈哈哈。</p>
<p><a style="background-color:black;color:white;text-decoration:none;padding:4px 6px;font-family:-apple-system, BlinkMacSystemFont, &quot;San Francisco&quot;, &quot;Helvetica Neue&quot;, Helvetica, Ubuntu, Roboto, Noto, &quot;Segoe UI&quot;, Arial, sans-serif;font-size:12px;font-weight:bold;line-height:1.2;display:inline-block;border-radius:3px" href="https://unsplash.com/@mparzuchowski?utm_medium=referral&amp;utm_campaign=photographer-credit&amp;utm_content=creditBadge" target="_blank" rel="noopener noreferrer" title="Download free do whatever you want high-resolution photos from Michał Parzuchowski"><span style="display:inline-block;padding:2px 3px"><svg xmlns="http://www.w3.org/2000/svg" style="height:12px;width:auto;position:relative;vertical-align:middle;top:-2px;fill:white" viewbox="0 0 32 32"><title>unsplash-logo</title><path d="M10 9V0h12v9H10zm12 5h10v18H0V14h10v9h12v-9z"/></svg></span><span style="display:inline-block;padding:2px 3px">Michał Parzuchowski</span></a></p>

        </div>
        
            <ul class="post-copyright">
            <li><strong>本文标题：</strong><a href="http://lokka.me/blog/problem/200408-n-queens/">N皇后（N-Queens）</a></li>
            <li><strong>本文作者：</strong><a href="http://lokka.me">Kain Zhang</a></li>
            <li><strong>本文链接：</strong><a href="http://lokka.me/blog/problem/200408-n-queens/">http://lokka.me/blog/problem/200408-n-queens/</a></li>
            <li><strong>发布时间：</strong>2020-04-08</li>
            <li><strong>版权声明：</strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明出处！
            </li>
            </ul>
            <br>
        
        
        <div class="level is-size-7 is-uppercase">
            <div class="level-start">
                <div class="level-item">
                    <span class="is-size-6 has-text-grey has-mr-7">#</span>
                    <!-- <i class="fas fa-tags has-text-grey"></i>&nbsp; -->
                    <a class="has-link-grey -link" href="/tags/BackTracking/" rel="tag">BackTracking</a>,&nbsp;<a class="has-link-grey -link" href="/tags/DFS/" rel="tag">DFS</a>,&nbsp;<a class="has-link-grey -link" href="/tags/Lanqiao/" rel="tag">Lanqiao</a>,&nbsp;<a class="has-link-grey -link" href="/tags/LeetCode/" rel="tag">LeetCode</a>
                </div>
            </div>
        </div>
        
        
        
    </div>
</div>



<div class="card">
    <div class="card-content">
        <h3 class="menu-label has-text-centered">Like this article? Support the author with</h3>
        <div class="buttons is-centered">
            
                
<a class="button is-success donate">
    <span class="icon is-small">
        <i class="fab fa-weixin"></i>
    </span>
    <span>Wechat</span>
    <div class="qrcode"><img src="/images/wechat.jpg" alt="Wechat"></div>
</a>

                
                <!-- Visit https://www.paypal.com/donate/buttons/ to get your donate button -->

<a class="button is-warning donate" onclick="document.getElementById(&#39;paypal-donate-form&#39;).submit()">
    <span class="icon is-small">
        <i class="fab fa-paypal"></i>
    </span>
    <span>Paypal</span>
</a>
<form action="https://www.paypal.com/cgi-bin/webscr" method="post" target="_blank" rel="noopener" id="paypal-donate-form">
    <input type="hidden" name="cmd" value="_donations" />
    <input type="hidden" name="business" value="E5US23TM56DQN" />
    <input type="hidden" name="currency_code" value="USD" />
</form>

                
                
<a class="button is-info donate">
    <span class="icon is-small">
        <i class="fab fa-alipay"></i>
    </span>
    <span>Alipay</span>
    <div class="qrcode"><img src="/images/alipay.jpg" alt="Alipay"></div>
</a>

                
        </div>
    </div>
</div>



<div class="card card-transparent">
    <div class="level post-navigation is-flex-wrap is-mobile">
        
        <div class="level-start">
            <a class="level level-item has-link-grey  article-nav-prev" href="/blog/designpattern/200425-factory-pattern/">
                <i class="level-item fas fa-chevron-left"></i>
                <span class="level-item">工厂模式（Factory Pattern）</span>
            </a>
        </div>
        
        
        <div class="level-end">
            <a class="level level-item has-link-grey  article-nav-next" href="/blog/diary/200401-diary/">
                <span class="level-item">First diary, Hello world!</span>
                <i class="level-item fas fa-chevron-right"></i>
            </a>
        </div>
        
    </div>
</div>


</div>
                




<div class="column is-4-tablet is-4-desktop is-3-widescreen  has-order-1 column-left ">
    
        
<div class="card widget">
    <div class="card-content">
        <nav class="level">
            <div class="level-item has-text-centered" style="flex-shrink: 1">
                <div>
                    
                    <figure class="image is-128x128 has-mb-6">
                        <img class="is-rounded" src="/images/hitomi.png" alt="Kain Zhang">
                    </figure>
                    
                    <p class="is-size-4 is-block">
                        Kain Zhang
                    </p>
                    
                    
                    <p class="is-size-6 is-block">
                        LIVE A LIFE YOU WILL REMEMBER
                    </p>
                    
                    
                    <p class="is-size-6 is-flex is-flex-center has-text-grey">
                        <i class="fas fa-map-marker-alt has-mr-7"></i>
                        <span>からっぽ島</span>
                    </p>
                    
                </div>
            </div>
        </nav>
        <nav class="level is-mobile">
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        Posts
                    </p>
                    <a href="/archives">
                        <p class="title has-text-weight-normal">
                            3
                        </p>
                    </a>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        Categories
                    </p>
                    <a href="/categories">
                        <p class="title has-text-weight-normal">
                            4
                        </p>
                    </a>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        Tags
                    </p>
                    <a href="/tags">
                        <p class="title has-text-weight-normal">
                            5
                        </p>
                    </a>
                </div>
            </div>
        </nav>
        
        <div class="level">
            <a class="level-item button is-link is-rounded" href="https://github.com/kainzhang" target="_blank" rel="noopener">
                <i class="fab fa-github"></i>&nbsp;
                Github
            </a>
        </div>
        
        
        
    </div>
</div>
    
        

    <!-- <div class="card widget" id="toc"> -->
    <div class="card widget column-left is-sticky" id="toc">
        <div class="card-content">
            <div class="menu">
                <h3 class="menu-label">
                    Catalogue
                </h3>
                <ul class="menu-list"><li>
        <a class="is-flex" href="#N-Queens">
        <span class="has-mr-6">1</span>
        <span>N-Queens</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#Description">
        <span class="has-mr-6">1.1</span>
        <span>Description</span>
        </a></li><li>
        <a class="is-flex" href="#Sample">
        <span class="has-mr-6">1.2</span>
        <span>Sample</span>
        </a></li><li>
        <a class="is-flex" href="#Thought">
        <span class="has-mr-6">1.3</span>
        <span>Thought</span>
        </a></li><li>
        <a class="is-flex" href="#Code">
        <span class="has-mr-6">1.4</span>
        <span>Code</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#Version-1">
        <span class="has-mr-6">1.4.1</span>
        <span>Version 1</span>
        </a></li><li>
        <a class="is-flex" href="#Version-2">
        <span class="has-mr-6">1.4.2</span>
        <span>Version 2</span>
        </a></li></ul></li></ul></li><li>
        <a class="is-flex" href="#N-Queen-II">
        <span class="has-mr-6">2</span>
        <span>N-Queen II</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#Description-1">
        <span class="has-mr-6">2.1</span>
        <span>Description</span>
        </a></li><li>
        <a class="is-flex" href="#Sample-1">
        <span class="has-mr-6">2.2</span>
        <span>Sample</span>
        </a></li><li>
        <a class="is-flex" href="#Thought-1">
        <span class="has-mr-6">2.3</span>
        <span>Thought</span>
        </a></li><li>
        <a class="is-flex" href="#Code-1">
        <span class="has-mr-6">2.4</span>
        <span>Code</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#2N-Queens">
        <span class="has-mr-6">3</span>
        <span>2N-Queens</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#Description-2">
        <span class="has-mr-6">3.1</span>
        <span>Description</span>
        </a></li><li>
        <a class="is-flex" href="#Sample-2">
        <span class="has-mr-6">3.2</span>
        <span>Sample</span>
        </a></li><li>
        <a class="is-flex" href="#Thought-2">
        <span class="has-mr-6">3.3</span>
        <span>Thought</span>
        </a></li><li>
        <a class="is-flex" href="#Code-2">
        <span class="has-mr-6">3.4</span>
        <span>Code</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#8-Queens">
        <span class="has-mr-6">4</span>
        <span>8-Queens</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#Description-3">
        <span class="has-mr-6">4.1</span>
        <span>Description</span>
        </a></li><li>
        <a class="is-flex" href="#Sample-3">
        <span class="has-mr-6">4.2</span>
        <span>Sample</span>
        </a></li><li>
        <a class="is-flex" href="#Thought-3">
        <span class="has-mr-6">4.3</span>
        <span>Thought</span>
        </a></li><li>
        <a class="is-flex" href="#Code-3">
        <span class="has-mr-6">4.4</span>
        <span>Code</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#Summary">
        <span class="has-mr-6">5</span>
        <span>Summary</span>
        </a></li></ul>
            </div>
        </div>
    </div>

    
    
        <div class="column-right-shadow is-hidden-widescreen ">
        
        </div>
    
</div>

                
            </div>
        </div>
    </section>
    <footer class="footer">
    <div class="container">
        <div class="level">
            <div class="level-start has-text-centered-mobile">
                <a class="footer-logo is-block has-mb-6" href="/">
                
                    <img src="/images/logo.svg" alt="N皇后（N-Queens）" height="28">
                
                </a>
                <p class="is-size-7">
                &copy; 2020 Kain Zhang&nbsp;
                Powered by <a href="https://hexo.io/" target="_blank" rel="noopener">Hexo</a> & <a
                        href="https://github.com/ppoffice/hexo-theme-icarus" target="_blank" rel="noopener">Icarus</a>
                
                </p>
            </div>
            <div class="level-end">
            
                <div class="field has-addons is-flex-center-mobile has-mt-5-mobile is-flex-wrap is-flex-middle">
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" rel="noopener" title="Creative Commons" href="https://creativecommons.org/">
                        
                        <i class="fab fa-creative-commons"></i>
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" rel="noopener" title="Attribution" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">
                        
                        <i class="fab fa-creative-commons-by"></i>
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" rel="noopener" title="Noncommericial" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">
                        
                        <i class="fab fa-creative-commons-nc"></i>
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" rel="noopener" title="Share Alike" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">
                        
                        <i class="fab fa-creative-commons-sa"></i>
                        
                    </a>
                </p>
                
                </div>
            
            </div>
        </div>
    </div>
</footer>
    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/min/moment-with-locales.min.js"></script>
<script>moment.locale("en");</script>


<script>
var IcarusThemeSettings = {
    site: {
        url: 'http://lokka.me',
        external_link: {"enable":true,"exclude":[]}
    },
    article: {
        highlight: {
            clipboard: true,
            fold: 'unfolded'
        }
    }
};
</script>


<script src="https://cdn.jsdelivr.net/npm/clipboard@2.0.4/dist/clipboard.min.js" defer></script>





<script src="/js/animation.js"></script>



<script src="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/js/lightgallery.min.js" defer></script>
<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js" defer></script>
<script src="/js/gallery.js" defer></script>



<div id="outdated">
    <h6>Your browser is out-of-date!</h6>
    <p>Update your browser to view this website correctly. <a id="btnUpdateBrowser" href="http://outdatedbrowser.com/">Update
            my browser now </a></p>
    <p class="last"><a href="#" id="btnCloseUpdateBrowser" title="Close">&times;</a></p>
</div>
<script src="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.js" defer></script>
<script>
    document.addEventListener("DOMContentLoaded", function () {
        outdatedBrowser({
            bgColor: '#f25648',
            color: '#ffffff',
            lowerThan: 'flex'
        });
    });
</script>


<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.5/unpacked/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
<script>
document.addEventListener('DOMContentLoaded', function () {
    MathJax.Hub.Config({
        'HTML-CSS': {
            matchFontHeight: false
        },
        SVG: {
            matchFontHeight: false
        },
        CommonHTML: {
            matchFontHeight: false
        },
        tex2jax: {
            inlineMath: [
                ['$','$'],
                ['\\(','\\)']
            ]
        }
    });
});
</script>


<a id="back-to-top" title="Back to Top" href="javascript:;">
    <i class="fas fa-chevron-up"></i>
</a>
<script src="/js/back-to-top.js" defer></script>














<script src="/js/main.js" defer></script>

    
    <div class="searchbox ins-search">
    <div class="searchbox-container ins-search-container">
        <div class="searchbox-input-wrapper">
            <input type="text" class="searchbox-input ins-search-input" placeholder="Type something..." />
            <span class="searchbox-close ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="searchbox-result-wrapper ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
    (function (window) {
        var INSIGHT_CONFIG = {
            TRANSLATION: {
                POSTS: 'Posts',
                PAGES: 'Pages',
                CATEGORIES: 'Categories',
                TAGS: 'Tags',
                UNTITLED: '(Untitled)',
            },
            CONTENT_URL: '/content.json',
        };
        window.INSIGHT_CONFIG = INSIGHT_CONFIG;
    })(window);
</script>
<script src="/js/insight.js" defer></script>
<link rel="stylesheet" href="/css/search.css">
<link rel="stylesheet" href="/css/insight.css">
    
<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"model":{"jsonPath":"/live2dw/assets/koharu.model.json"},"display":{"position":"right","width":225,"height":350},"mobile":{"show":false,"scale":0.7},"log":false,"pluginJsPath":"lib/","pluginModelPath":"assets/","pluginRootPath":"live2dw/","tagMode":false});</script></body>
</html>